1. Technical Field
The present invention relates to improved methods and systems for reliable information-retrieval and updating. In particular, the present invention relates to improved methods and systems for reliable information-retrieval and data (or information) updating in distributed computer networks. More particularly, the present invention relates to improved methods and systems for reliable information-retrieval and data (or information) updating in distributed computer networks via a consistent ordering of client requests.
2. Description of the Related Art
Computer networks allow users of data-processing systems to link with remote servers, and thus retrieve vast amounts of electronic information heretofore unavailable in an electronic medium. Computer networks are increasingly displacing more conventional means of information transmission, such as newspapers, magazines, and television. A computer network connects a set of machines and allows them to communicate with one another. In such a computer network, one machine may act as a gateway that connects the computer network to other networks. The gateway handles data transfer and the conversion of messages from a sending network to protocols utilized by a receiving network.
A set of computer networks can be combined to form a so-called "Internet" when connected with one other directly or indirectly via gateways. The term "Internet" is an abbreviation for "Inter-network," and refers commonly to the collection of networks and gateways that utilize the TCP/IP suite of protocols, which are well-known in the art of computer networking. TCP/IP is an acronym for "Transport Control Protocol/Internet Protocol," a software protocol developed by the Department of Defense for communication between computers. In recent years, the Internet has allowed users to interact and share information over the networks. Because of such wide-spread information sharing, the Internet has thus generally evolved into an "open" system in which developers can design software applications for performing specialized operations or services, essentially without restriction.
Typical networked systems utilized widely today follow a client/server architecture. In network computing, a client is a process (i.e., roughly a program or task) that requests a service provided by another program, the server. The client process may utilize the requested service without having to "know" the working details of the other program or the requested service itself. In a client/server architecture, particularly a networked system, a client is usually a computer that accesses shared network resources provided by another computer (i.e., a server).
A client/server architecture acts as a framework for distributed applications that organize the flow of information between clients and servers. For example, in a stock-quotation service, a client sends requests to the server over the Internet, identifying a particular stock name. The server retrieves the desired information from one or more associated storage devices, and sends back an appropriate reply to the client over the network. This form of interaction between the client and the server is referred to as "information retrieval."
Equivalently, some sets of clients may transmit requests to update the information stored at a server storage devices. For example, a computer utilized within a stock market environment may send information to a server to refresh current stock prices. Alternatively, in the same stock market environment, a client may interact with a server in an electronic business framework to update relevant information stored at the service storage device (e.g. a stock portfolio account). This form of interaction between the client and server is referred to as "information update" or "information updating." Generally, the client process may be active in a first computer system, and the server process may be active in a second computer system, thereby communicating with one another over a computer network, while providing distributed functionality and permitting multiple clients to take advantage of the information-gathering capabilities of the server.
Such client/server architectures are often configured as distributed computer networks in which distributed servers achieve reliability and high availability utilizing replication. In such systems, several processors or machines may be utilized to provide a service, with each machine replicating the state of the service. Such machines are referred to as "server replicas" or simply "replicas". A client may communicate with a subset of server replicas to obtain and update information. Such a subset may include all, some, or only one of the available replicas. A client may select the subset randomly or via pre-defined selection criteria. It is thus necessary that all server replicas maintain identical states in order to ensure a consistent view of the information manipulated by the service, as perceived by the same client or by different clients.
If a server replica fails, the remaining server replicas continue to operate, thereby ensuring uninterrupted service for the clients. A significant problem faced by designers in implementing replicated services is to ensure that replicas maintain identical states that reflect client transactions with the service. For example, two different clients may issue an update request to the same record in a database maintained by a replicated service. If the two requests are processed in different order by two or more different replicas, the values of the record may be inconsistent at different replicas.
Ordered multicast protocols have attempted to address this problem. Ordered multicast protocols ensure that all server replicas receive the same messages from the network in the same order, thereby guaranteeing that the server replicas process identical requests and maintain identical states. A multicast protocol guarantees that all server replicas receive all client requests, even if the clients are communicating with only a subset of the servers. Commercial products that benefit from such protocols include "Web" servers, on-line transaction processing systems, stock market quotation services, general purpose file systems, electronic business servers, and so forth.
Multicast protocols do, however, impose a performance penalty because such protocols must be processed in a manner to ensure that clients requests are delivered in the same order at all server replicas. An ordering protocol requires server replicas to exchange special-purpose messages, which in turn may consume network bandwidth and delay the delivery of a request to a server program until an agreement is reached regarding the delivery order. The server program cannot begin processing the request until the ordering protocol completes its operation. The resulting performance penalty translates into a decline in communication throughput and an increase in response time. A rapid response time is increasingly necessary for successful operation in interactive client/server systems, such as Web servers, electronic business transaction services, or interactive services. Rapid response times are increasingly difficult to achieve in such interactive client/server systems utilizing traditional multicast protocols.
Based on the foregoing, it can be appreciated that a need exists for an improved method and system for implementing an ordering protocol that ensures all replicas of a server receive client requests in the same order, while offering better response time than traditional multicast protocols. It is believed that the invention described herein addresses and solves these problems.